#include"Sort.h"
#include"Stack.c"

void PrintArray(int* a, int n)
{
    for(int i = 0; i < n; i++)
    {
        printf("%d", a[i]);
    }
    printf("\n");
};

void InsertSort(int* a, int n)//插入排序 时间复杂度O(n^2) 空间复杂度O(1)
{
    for(int i = 0;i < n - 1; i++)  //i < n - 1是因为要预留出往后移的位置
    {
        int end = i;
        int tmp = a[i + 1];        //tmp是往前比较的数
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                end--;
            }
            else break;
        }
        a[end + 1] = tmp;
    }
}

void Swap(int* a, int* b)
{
    int* tmp = a;
    int* a = b;
    int* b = tmp;
}

void BubbleSort(int* a, int n)//冒泡排序
{
    int exchange = 0;
    for (int j = 0; j < n; j++)
    {
        for(int i = 0; i < n - 1; i++)
        {
            if(a[i] > a[i + 1])
            {
                Swap(&a[i], &a[i + 1]);
                exchange++;
            }
        }
        if (exchange == 0)       //完成一遍排序后exchange仍然为0 说明已经有序排列，可以跳出循环
        {
            break;
        }
    }   
}
void ShellSort(int* a, int n)//希尔排序  时间复杂度O(n^1.3) 空间复杂度O(1)
{
    int gap = n;

    while (gap > 1)
    {
        gap /= 2;  //下面直接按照插入排序 最小单位由1改为gap
        for (int i = 0; i < n - gap; i++)
        {
           int end = i;
           int tmp = a[end + gap];
           while (end >= 0)
           {
            if (tmp < a[end])
            {
                a[end] = a[end + gap];
                end -= gap;
            }
            else break;
           }
           a[end + gap] = tmp;
        }
    }
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 假设法，选出左右孩子中小的那个孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)//堆排序 时间复杂度O(N*logN)
{
    //对数组直接建堆
    for (int i = (n - 1 - 1) / 2; i >= 0;i--)
    {
        AdjustDown(a, n, i);
    }

    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}

void SelectSort(int* a, int n)//选择排序 选出最大最小的数放到数组两边
{
    int begin = 0;
    int end = n - 1;

    while (begin < end)
    {
        int mini, maxi = begin;

        for (int i = begin + 1; i <= end; i++)
        {
            if (a[i] < a[mini])
            {
                mini = i;
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }
        }
        Swap(&a[begin], &a[mini]);
        if ( maxi == begin)
        {
            maxi = mini;
        }
        Swap(&a[end], a[maxi]);
        begin++;
        end--;
    }
}

void QuickSort1(int* a, int left, int right)//快速排序（Hoare版本） 时间复杂度O(N*logN) 空间复杂度O(logN)
{
    if (left >= right)
    {
        return;
    }

    int begin = left, end = right;
    int keyi = left;

    while (left < right)
    {
        // right先走找小，left先走找大（升序）
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        while (left<= right && a[left] <= a[keyi])
        {
            left++;
        }
        Swap(&a[left], a[right]);
    }

    Swap(&a[left], &a[keyi]);
    keyi = left;

    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1,end);
}

void QuickSort2(int* a, int left, int right)
{
    if (left >= right)
    {
        return;
    }

    int keyi = left;
    int prev = left;
    int cur = left + 1;

    while (cur <= right)
    {
        if (a[cur] < a[keyi])
        {
            prev++;
            Swap (&a[prev], &a[cur]);
        }
        cur++;
    }

    Swap(&a[keyi], &a[prev]);
    keyi = prev;

    QuickSort2(a, left, keyi - 1);
    QuickSort2(a, keyi + 1, right);

}

/*
Hoare方法的优化：
1.小区间优化：
          if (right - left + 1 < 10)
	          {
		          InsertSort(a + left, right - left + 1);
	          }
              这个方法可以减少90%左右的递归
2.随机选key或三数中选key
int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	//printf("%d %d %d", left, mid, right);
	//printf("->%d %d %d\n", a[left], a[mid], a[right]);

	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
这个函数用来选三数中大小中间的数，把排序数组的头尾和中间的数选择居中的作为key
*/

//非递归的快速排序：
void QuickSortNonR(int* a, int left, int right)
{
    ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);

    while (!STEmpty(&st))
    {
        int begin = STTop(&st);
        STPop(&st);

        int end = STTop(&st);
        STPop(&st);

        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        
        while (cur <= end)  //走一个单趟
		{
			if (a[cur] < a[keyi] && ++prev != cur)
				Swap(&a[prev], &a[cur]);

			++cur;
		}

		Swap(&a[keyi], &a[prev]);
		keyi = prev;

        if (keyi + 1 < end)
        {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }

        if (begin < keyi - 1)
        {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }

    STDestroy(&st);
}

//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if (begin == end)
        return;

        int mid = (begin + end) / 2;
        _MergeSort(a, begin, mid, tmp);
        _MergeSort(a, mid + 1, end, tmp);

        int begin1 = begin,end1 = mid;
        int begin2 = mid + 1, end2 = end;
        int i = begin;

        while (begin1 <= end && begin2 <= end2)
        {
            if (a[begin1] < a[begin2])
            {
                tmp[i++] = a[begin1];
            }

            else
            {
                tmp[i++] = a[begin2];
            }
        }

        while (begin1 <= end1)
        {
            tmp[i++] = a[begin1++];
        }
        while (begin2 <= end1)
        {
            tmp[i++] = a[begin2++];
        }
        
       memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n) //时间复杂度O(N*logN) 空间复杂度O(N)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }

    _MergeSort(a, 0, n - 1, tmp);

    free(tmp);
    tmp = NULL;
}

//归并排序的非递归版本
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;

	while (gap < n)
	{
		//printf("gap:%d->", gap);
		for (int j = 0; j < n; j += 2 * gap)
		{
			int begin1 = j, end1 = begin1 + gap - 1;
			int begin2 = begin1 + gap, end2 = begin2 + gap - 1;
			//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

			// 越界的问题处理
			if (end1 >= n || begin2 >= n)
				break;

			if (end2 >= n)
				end2 = n - 1;

			int i = j;
			// 依次比较，取小的尾插tmp数组
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[i++] = a[begin1++];
				}
				else
				{
					tmp[i++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[i++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[i++] = a[begin2++];
			}

			memcpy(a + j, tmp + j, sizeof(int) * (end2-j+1));
		}

		//printf("\n");

		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}